//package com.huajin.codetest.collection.soucre;
//
//public class ConcurrentHashMap<K, V> {
//	
//	 /* ---------------- Constants -------------- */
//	
//	static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
//	
//	 /* ---------------- Fields -------------- */
//
//    /**
//     * The array of bins. Lazily initialized upon first insertion.
//     * Size is always a power of two. Accessed directly by iterators.
//     */
//    transient volatile Node<K,V>[] table;
//    
//    /* ---------------- Nodes -------------- */
//
//    /**
//     * Key-value entry.  This class is never exported out as a
//     * user-mutable Map.Entry (i.e., one supporting setValue; see
//     * MapEntry below), but can be used for read-only traversals used
//     * in bulk tasks.  Subclasses of Node with a negative hash field
//     * are special, and contain null keys and values (but are never
//     * exported).  Otherwise, keys and vals are never null.
//     */
//    static class Node<K,V> implements Map.Entry<K,V> {
//        final int hash;
//        final K key;
//        volatile V val;
//        volatile Node<K,V> next;
//
//        Node(int hash, K key, V val) {
//            this.hash = hash;
//            this.key = key;
//            this.val = val;
//        }
//
//        Node(int hash, K key, V val, Node<K,V> next) {
//            this(hash, key, val);
//            this.next = next;
//        }
//
//        public final K getKey()     { return key; }
//        public final V getValue()   { return val; }
//        public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
//        public final String toString() {
//            return Helpers.mapEntryToString(key, val);
//        }
//        public final V setValue(V value) {
//            throw new UnsupportedOperationException();
//        }
//
//        public final boolean equals(Object o) {
//            Object k, v, u; Map.Entry<?,?> e;
//            return ((o instanceof Map.Entry) &&
//                    (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
//                    (v = e.getValue()) != null &&
//                    (k == key || k.equals(key)) &&
//                    (v == (u = val) || v.equals(u)));
//        }
//
//        /**
//         * Virtualized support for map.get(); overridden in subclasses.
//         */
//        Node<K,V> find(int h, Object k) {
//            Node<K,V> e = this;
//            if (k != null) {
//                do {
//                    K ek;
//                    if (e.hash == h &&
//                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
//                        return e;
//                } while ((e = e.next) != null);
//            }
//            return null;
//        }
//    }
//    
//    /* ---------------- Static utilities -------------- */
//    
//    /**
//     * Spreads (XORs) higher bits of hash to lower and also forces top
//     * bit to 0. Because the table uses power-of-two masking, sets of
//     * hashes that vary only in bits above the current mask will
//     * always collide. (Among known examples are sets of Float keys
//     * holding consecutive whole numbers in small tables.)  So we
//     * apply a transform that spreads the impact of higher bits
//     * downward. There is a tradeoff between speed, utility, and
//     * quality of bit-spreading. Because many common sets of hashes
//     * are already reasonably distributed (so don't benefit from
//     * spreading), and because we use trees to handle large sets of
//     * collisions in bins, we just XOR some shifted bits in the
//     * cheapest possible way to reduce systematic lossage, as well as
//     * to incorporate impact of the highest bits that would otherwise
//     * never be used in index calculations because of table bounds.
//     */
//    //-- 计算当前Node的hash值的方法
//    static final int spread(int h) {
//    	//-- 将key的hashCode值得高低16位进行^运算，最终又与HASH_BITS进行了&运算
//        return (h ^ (h >>> 16)) & HASH_BITS;
//    }
//    
//    public V put(K key, V value) {
//        return putVal(key, value, false);
//    }
//
//    /** Implementation for put and putIfAbsent */
//    final V putVal(K key, V value, boolean onlyIfAbsent) {
//    	//-- ConcurrentHashMap不允许key或者value出现为null的值，跟HashMap的区别
//        if (key == null || value == null) throw new NullPointerException();
//        //-- 根据key的hashCode计算出一个hash值，后期得出当前key-value要存储在哪个数组索引位置
//        int hash = spread(key.hashCode());
//        //-- 一个标识
//        int binCount = 0;
//        
//        
//        
//        
//        
//        
//        
//        
//        for (Node<K,V>[] tab = table;;) {
//            Node<K,V> f; int n, i, fh; K fk; V fv;
//            if (tab == null || (n = tab.length) == 0)
//                tab = initTable();
//            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
//                    break;                   // no lock when adding to empty bin
//            }
//            else if ((fh = f.hash) == MOVED)
//                tab = helpTransfer(tab, f);
//            else if (onlyIfAbsent // check first node without acquiring lock
//                     && fh == hash
//                     && ((fk = f.key) == key || (fk != null && key.equals(fk)))
//                     && (fv = f.val) != null)
//                return fv;
//            else {
//                V oldVal = null;
//                synchronized (f) {
//                    if (tabAt(tab, i) == f) {
//                        if (fh >= 0) {
//                            binCount = 1;
//                            for (Node<K,V> e = f;; ++binCount) {
//                                K ek;
//                                if (e.hash == hash &&
//                                    ((ek = e.key) == key ||
//                                     (ek != null && key.equals(ek)))) {
//                                    oldVal = e.val;
//                                    if (!onlyIfAbsent)
//                                        e.val = value;
//                                    break;
//                                }
//                                Node<K,V> pred = e;
//                                if ((e = e.next) == null) {
//                                    pred.next = new Node<K,V>(hash, key, value);
//                                    break;
//                                }
//                            }
//                        }
//                        else if (f instanceof TreeBin) {
//                            Node<K,V> p;
//                            binCount = 2;
//                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
//                                                           value)) != null) {
//                                oldVal = p.val;
//                                if (!onlyIfAbsent)
//                                    p.val = value;
//                            }
//                        }
//                        else if (f instanceof ReservationNode)
//                            throw new IllegalStateException("Recursive update");
//                    }
//                }
//                if (binCount != 0) {
//                    if (binCount >= TREEIFY_THRESHOLD)
//                        treeifyBin(tab, i);
//                    if (oldVal != null)
//                        return oldVal;
//                    break;
//                }
//            }
//        }
//        addCount(1L, binCount);
//        return null;
//    }
//    
//    
//    
//    
//
//}
